package com.linwen.excise.sort;

import com.linwen.javase.MyPrint;

import java.util.Arrays;

/**
 * 基数排序
 *
 * @author : linwen
 * @date : 下午3:54 2021/6/13
 */
public class _08RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{123,45,345,157,485,354,987,980};
        radixSirt(arr);
        MyPrint.print();
        MyPrint.print(arr);
    }

    private static void radixSirt(int[] arr) {
        //计数数组
        int[] count = new int[10];
        int[] result = new int[arr.length];
        int h=1;
        for(int loop=0;loop<3;loop++) {
            for (int i = 0; i < arr.length; i++) {
                count[arr[i] / h % 10]++;
            }
            System.out.println();
            System.out.println("计数数组"+Arrays.toString(count));
            //累加数组
            for (int i = 1; i < count.length; i++) {
                count[i] = count[i] + count[i - 1];
            }
            System.out.println();
            System.out.println("累加数组"+Arrays.toString(count));
            for (int i = arr.length - 1; i >= 0; i--) {
                int num = arr[i] / h % 10;
                result[count[num] - 1] = arr[i];
                count[num]--;
            }
            System.out.println();
            System.out.println("临时结果数组"+Arrays.toString(result));
            h *= 10;
            //清空count
            Arrays.fill(count,0);
            //result-->arr
            System.arraycopy(result,0,arr,0, arr.length);
            System.out.println();
            System.out.println("结果数组"+Arrays.toString(arr));
        }

    }
}
